perm filename BIN[0,BGB]6 blob
sn#115056 filedate 1974-08-12 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00008 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 {F3⊂C<Nα POLYHEDRON INTERSECTION.λ30P50I425,0JCFA} SECTION 5.
C00006 00003 ⊂5.1 Intersection Geometry.⊃
C00010 00004 ⊂5.2 Intersection Topology.⊃
C00015 00005 ⊂5.3 Special Cases.⊃
C00018 00006 ⊂5.4 Face Convexity Coercion.⊃
C00020 00007 ⊂5.5 Body Cutting.⊃
C00021 00008 ⊂5.6 Performance and Related Work.⊃
C00022 ENDMK
C⊗;
{F3;⊂C;<N;α POLYHEDRON INTERSECTION.;λ30;P50;I425,0;JCFA} SECTION 5.
{JCFD} POLYHEDRON INTERSECTION.
{λ10;W250;JAFA}
5.0 Introduction to Polyhedron Intersection.
5.1 Intersection Geometry.
5.2 Intersection Topology.
5.4 Special Cases of Intersection.
5.5 Face Convexity.
5.6 Body Cutting.
5.7 Performance and Related Work.
{λ30;W0;I950,0;JUFA}
⊂5.0 Introduction to Polyhedron Intersection.⊃
The intersection, union and set differences of two solid
polyhedra can be computed by combining a body interection procedure
called BIN with the EVERT primitive, as figure 5.1 illustrates. The
body intersection procedure is important for three reasons: first, it
is a general and conceptually elegant construction operator; second,
it can be used for spatial modeling in collision detection and
trajectory planning for manipulators and vehicles; and third, it can
be used to localize an object in 3-D space from a sequence of
silhouette views. The intersection algorithm consists of two parts:
first, there is a geometric part in which all the faces and edges are
compared with each other for potential face/edge intersections called
piercing points; and second, there is a topological part in which the
results are "copied off" of the given polyhedra; the results may
consist of zero, one or many polyhedra. In the following, the "operands"
refers to the sets of polyhedra given to BIN as arguments and the "result"
refers to the set (possibly empty) of polyhedra produced by BIN.{Q}
{I660,0;FCJC} FIGURE 5.1 - POLYHEDRON INTERSECTION, UNION AND SUBTRACTION.{
H3;X0.61;I300,630;*BIN1.PLT;
I565,0;JC;FA} TWO OPERANDS: STAR AND CYLN{
I650,1;⊗BIN2.PLT;I∂0,∂630;⊗BIN3.PLT; I∂580,120;
}INTERSECTION: BIN(STAR,CYLN){I∂0,650;
}UNION: EVERT(BIN(EVERT(STAR),EVERT(CYLN))){
I1250,1;⊗BIN4.PLT;I∂0,∂630;⊗BIN5.PLT;I∂580,70;
}SUBTRACTION: BIN(EVERT(STAR),CYLN){I∂0,690;
}SUBTRACTION: BIN(STAR,EVERT(CYLN)){JUFAQ}
⊂5.1 Intersection Geometry.⊃
The geometric part of the polyhedron intersection algorithm,
BIN, conceptually consists of comparing each face of one argument
with every edge of the other argument and vice versa. In practice
the potentially N-squared compares are avoided by using the same
recursive window partition sort that was used in the hidden line
eliminator, OCCULT (subsection 4.3). Ignoring the recursive windowing
for a moment, the inner most face-edge compare of BIN consists of
four steps: opposition, intersection, enclosure and fission.
<Opposition Test>. Given a face F and an edge E, first, the
endpoints of the edge are checked to see whether they are in opposite
halfspaces with respect to the plane of the face. In terms of vector
geometry, the dot product of the face vector and each vertex vector
is taken and the signs compared; different signs indicate that the
vertices are in different halfspaces. The opposition test requires
six multiplications. <Intersection Locus>. The locus of the point
where the edge pierces the plane of the face is computed. <Enclosure
Test>. Next the edge is tested to see if it actually passes thru the
interior of the face. In BIN, this test exploits the face convexity
restriction. The test consists of crossing neighboring pairs of
vectors radiating from the face plane piercing point to each vertex
of the given face and testing for a sign change. In practice, only
one component of the cross product needs be evaluated and so only two
multiplications per edge of the face are required. <Edge Fission>. If
the edge pierces the face, then the edge is split (using the ESPLIT
and BLED routines) forming a new vertex, called a face piercing
vertex. A temporary link of the vertex (left half of word 7) is set
to point at the face that was pierced and the PED link of the new
vertex is set to point at the one of its two edges that is external to
the surface.
FIGURE 5.2 - FACE PIERCING GEOMETRY.
{Q}
⊂5.2 Intersection Topology.⊃
After all the face piercing vertices have been made (assuming
no pathological cases, see section 5.3), the edges and vertices of
the result can be created in relation to the faces,
edges, and vertices of the given polyhdera.
However in order to explain the details of the
relationship three definitions are needed:
"interior", "surface" and "surface loop".
In figure 5.3, two solid hexahedrons are being intersected,
on the left the surface loop of the intersection is
intensified (heavy lined) on the right the interior edges are intensified.
{FCJC} FIGURE 5.3 - SURFACE EDGES AND INTERIOR EDGES OF RESULT. {JUFA}
In particular, each
piercing vertex has a corresponding vertex which is a trihedral
corner of the result.
The correspondence is maintained in a temporary link field named
ALT; the alternate vertices and edges that belong to the result are
created by two topological trace routines: the MKSURF routine, which
makes surface edges and vertices of the result starting its surface
loop trace when given "un-ALT'ered" face piercing vertex; and the
ETRACE routine, which makes edges and vertices interior to the result
polyhedron by tracing the edge graph bounded by pierce vertices. The
new result edges are temporarily linked to the old operand faces. The
MKSURF and ETRACE routines are followed by three steps that fixup
surface wings, interior wings and face nodes so that a legally formed
result polyhedron is completed.
{FCJC} FIGURE 5.4 - FETCH OTHER PIERCE-VERTEX OF A FACE. {JUFA}
Fixup step-1 places vertex and wing pointers in all the
non-surface edges. A non-surface edge is distinguished by its
non-zero ALT link, and the new vertices are provided with an A as a
first edge, PED, if it be lacking.
{λ10;JAF3} A←BODY0;
WHILE (A←PED(A)) ≠ BODY0 DO IF (E←ALT(A))≠0 THEN
BEGIN
PVT(A) ←V← ALT(PVT(E)); IF PED(V)=0 THEN PED(V)←A;
NVT(A) ←V← ALT(NVT(E)); IF PED(V)=0 THEN PED(V)←A;
NCW(A) ← ALT(NCW(E));
PCW(A) ← ALT(PCW(E));
NCCW(A) ← ALT(NCCW(E));
PCCW(A) ← ALT(PCCW(E));
END;
{λ30;JUFA}
Fixup step-2 wings together the surface vertex tridedral
corners. Since by good luck all surface vertices are necessarily
trihedral, the edges can be passed to the WING primitive for oriented
linking, in any order. The two surface wings of a surface vertex
were stored in the NED and PED links by MKSURF; the inward wing can
be retrieve as the PED(ALT(U)). Surface vertices are distinguished by
their ALT vertex having his SURBIT on.;
Fixup step-3 replaces the alein faces of the result body with
native faces; this is done by scaning the edge ring of the body,
testing the two faces of each edge to see if they belong to the
result body, and if a face doesn't belong it is replaced by a new
one. Face replacement, as ususal, requires clocking around a face
perimeter and changing the appropriate face link in each edge.
⊂5.3 Special Cases.⊃
In order of difficulty from easy to hard, the four special
cases that must be handled are non-intersection, extremely short
edges, face holes and coincident entities. ~<Non-Intersection>~.
When the face-edge compare (by recursive window spacee sort) returns
no piercing points, it implies that the surfaces of the given
polyhedra do not intersect and that a further test is needed to
determine whether the operands are disjoint (and so the intersection
be empty) or whether one operand contains the other. ~<Face Holes>~.
Because EVERT'ed solids are allowed, one polyhedron can cut a hole
in a face of the other without intersecting any of the edges of that
face, which would fool the copy-trace. So as a preliminary step to
BIN, all the surface loops are traced and checked to make certain
they cross more than one face. If a one face surface-loop is found,
the face is pyramided to a vertex interior to the surface-loop.
~<Short Edges>~. An application of BIN can create edges with almost
zero length, which require an extra pass to find and delete.
~<Coincidant Entities>~. Even though an occassional edge that lies
exactly in the plane of a face can be fudged off in a random
direction and the resulting extremely short edges supressed; it is
meaningful to try to intersect two polyhedra which have many faces,
edges and vertices that are exactly coincident - which usually causes
the present implementation to fail.
{FCJC} FIGURE 5.5 - EXAMPLE OF FACE HOLE FIXUP. {JUFA}
⊂5.4 Face Convexity Coercion.⊃
Since, both the body intersection method, BIN, and the hidden
line eliminator, OCCULT, are restricted to convex face polyhdera; it
is essential to have a method that detects and subdivides the concave
faces of a given polyhedron. The routine MKCNVX, make convex, reduces
the concave faces of a body into reasonible convex faces. The whole
method consists of two steps: first, the face is broken down into
triangles and second, the longest unnecessary new edges are removed.
The atomization to triangles step is recursive: the pointiest extrema
vertex, V0, is lopped off, if no other vertices of the face are on
the same side of the line segment between V0's immediate neighboring
vertices: OTHER(ECCW(V0,F),V0) and OTHER(ECW(V0,F),V0). An extrema
vertex is one that touchs the smallest circumscribed rectangle whoes
sides are parellel to the coordinate axes; the pointiest vertex is
the one with the largest cosine. This make-convex method is craft
that was evolved without benefit of theory. The performance of the
method is startlingly good, it automatically convexes polygons the
same way that I would.
{FCJC} FIGURE 5.6 - EXAMPLES OF FACE CONVEXITY COERCION. {JUFA}
⊂5.5 Body Cutting.⊃
Body cutting is the operation of dividing an arbitrary
polyhedron into sets of parts above and below a given cutting plane.
Although cutting is simply a special case of polyhedron intersection,
the process is sufficiently important and different to merit a
separate implementation.
{FCJC} FIGURE 5.7 - BODY CUTTING ILLUSTRATED. {JUFA}
⊂5.6 Performance and Related Work.⊃